#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:

    // 712. 两个字符串的最小ASCII删除和
    // https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
    int minimumDeleteSum(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        int sum = 0;

        for (int i = 1; i<=n; ++i)
        {
            for (int j = 1; j<=m; ++j)
            {
                if (s1[i-1] == s2[j-1])
                    dp[i][j] = dp[i-1][j-1] + s1[i-1];
                else
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            }
            sum += s1[i-1];
        }

        for (auto ch : s2)
            sum += ch;
        
        return sum - 2*dp[n][m];
    }

    // 718. 最长重复子数组
    // https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        int ans = 0;

        for (int i = 1; i<=n; ++i)
        {
            for (int j = 1; j<=m; ++j)
            {
                if (nums1[i-1] == nums2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                ans = max(ans, dp[i][j]);
            }
        }

        return ans;
    }
};